| 翻訳と辞書 |
RAC drawing
In graph drawing, a RAC drawing of a graph is a drawing in which the vertices are represented as points, the edges are represented as straight line segments or polylines, at most two edges cross at any point, and when two edges cross they do so at right angles to each other. In the name of this drawing style, "RAC" stands for "right angle crossing".
The right-angle crossing style and the name "RAC drawing" for this style were both formulated by ,〔.〕 motivated by previous user studies showing that crossings with large angles are much less harmful to the readability of drawings than shallow crossings.〔.〕 Even for planar graphs, allowing some right-angle crossings in a drawing of the graph can significantly improve measures of the drawing quality such as its area or angular resolution.〔.〕
==Examples==
The complete graph ''K''5 has a RAC drawing with straight edges, but ''K''6 does not. Every 6-vertex RAC drawing has at most 14 edges, but ''K''6 has 15 edges, too many to have a RAC drawing.〔
A complete bipartite graph ''K''''a'',''b'' has a RAC drawing with straight edges if and only if either min(''a'',''b'') ≤ 2 or ''a'' + ''b'' ≤ 7. If min(''a'',''b'') ≤ 2, then the graph is a planar graph, and (by Fáry's theorem) every planar graph has a straight-line drawing with no crossings. Such a drawing is automatically a RAC drawing. The only two cases remaining are the graphs ''K''3,3 and ''K''3,4. A drawing of ''K''3,4 is shown; ''K''3,3 can be formed from it by deleting one vertex. Neither of the next two larger graphs, ''K''4,4 and ''K''3,5, has a RAC drawing.〔.〕
抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』
■ウィキペディアで「RAC drawing」の詳細全文を読む
スポンサード リンク
| 翻訳と辞書 : 翻訳のためのインターネットリソース |
Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.
|
|